/*
Problem:    Decode ways
Notes:
A message containing letters from A-Z is being encoded to numbers using
the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of
ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.
*/

#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    int numDecodings(string s) {
    	if (s.size() == 0)
    		return 0;
    	int last_2 = 1;
    	int last_1 = 1;
    	for (int i = 1; i < s.size(); i++) {
    		int num = last_1;
    		if (s[i-1] < '3' && s[i] < '7') {
    			num += last_2;
    		}
    		last_2 = last_1;
    		last_1 = num;
    	}

    	return last_1;

    }
};



int main(int argc, char* argv[])
{
	Solution s;
	cout << s.numDecodings("12") << endl;
	cout << s.numDecodings("122") << endl;
	cout << s.numDecodings("1272") << endl;
	cout << s.numDecodings("12722") << endl;
	return 0;
}